package wy;

public class Test_erfenfa {

    public static void main(String[] args) {
        int[] arr = {11, 22, 33, 44, 55, 66, 77};
        int i = getIndex(arr, 33);
        System.out.println(i);
        i = search(arr,33);
        System.out.println(i);
    }

    public static int getIndex(int[] arr, int value) {
        int min = 0;
        int max = arr.length - 1;
        int mid = (min + max) / 2;

        while (arr[mid] != value) {                    //当中间值不等于要找的值,就开始循环查找
            if (arr[mid] < value) {                    //当中间值小于了要找的值
                min = mid + 1;                    //最小的索引改变
            } else if (arr[mid] > value) {            //当中间值大于了要找的值
                max = mid - 1;                    //最大的索引改变
            }

            mid = (min + max) / 2;                    //无论最大还是最小改变,中间索引都会随之改变

            if (min > max) {                        //如果最小索引大于了最大索引,就没有查找的可能性了
                return -1;                    //返回-1
            }
        }
        return mid;
    }

    static int search(int A[], int num) {
        int left = 0;
        int right = A.length - 1;
        int mid = 0;
        int pos = -1;    //返回-1，表示查找失败

        while (left <= right) {
            mid = (left + right) / 2;

            if (A[mid] == num) {
                pos = mid;
                break;
            }
            if (A[left] <= A[mid])    //前半部分是严格递增的，后半部分是一个更小的循环递增数组
            {
                if (A[left] <= num && num < A[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else    //后半部分是严格递增的，前半部分是一个更小的循环递增数组
            {
                if (A[mid] < num && num <= A[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return pos;
    }
}
